The growth of the Internet during the 1990s was the driving force behind the three generations of Internet Protocol (IP) routers. The development is underway of fourth generation routers, which include more optics and a higher degree of parallelism. While Internet bandwidth is no longer growing at triple digit rates, it is still growing at a respectable 60-70% per year. This is a seemingly sustainable growth, which exceeds Moore's law by a significant margin.
To match this demand, vendors are delivering faster IP core routers that implement optical interfaces and electronic switching matrices to accommodate the inexorable growth in Internet traffic. The next evolution of the core network has an IP layer at the edge of a circuit-switched optical layer based on wave division multiplexing (WDM) circuits with optical cross connects. However, there is reason to be concerned about the ability of primarily electronic IP routers to keep pace with the bandwidth growth provided by the switched optical layer.
A packet switch that is fully optical requires a technological evolution that is currently just a promise. Many of the enabling technologies are still in the stage of research and experimentation. So, while optical switching may be deployed in the future, it is not expected to come soon enough to handle nearer term bandwidth needs. Thus, there will be a gap between Internet bandwidth needs and the bandwidth capabilities of primarily electronic IP routers before 100% optical packet switches become practical. In the near term, switch routers have the option of being simpler, using more optics, and taking advantage of increased parallelism.
However, the issue of maintaining packet sequencing in fourth generation routers is becoming more problematic. Most conventional high performance packet switches use input queuing and a non-blocking (e.g., crossbar) switch fabric. Thin input queues are arranged as virtual output queues (VOQs) to overcome head of line blocking and to enable high throughput rates. To simplify the task of memory management, a fixed-sized time slot is used. This requires the segmenting of incoming variable length packets into fixed-sized cells. A centralized scheduler examines each slot of the VOQ to determine the configuration of the switch fabric for the next time slot. These switch fabrics generally have a scheduler-based forwarding mechanism. A hot standby mode switch fabric provides redundancy.
There has been significant work in the area of parallel operating switch fabrics. However, there has been limited work on maintaining packet sequencing in systems using such parallel operating switch fabrics. In 2001, Iyer and McKeown suggested using a line buffer to reorder mis-sequenced data packets. In June 2002, Keslassy and McKeown proposed a “full frames first” (FFF) mechanism that eliminates the sequencing buffer by avoiding data packet mis-sequencing. The FFF mechanism uses a three-dimensional variant of the virtual output queue and a set of deterministic sequences that connect inputs to outputs to achieve this feat. However, all of the proposed solutions are complex and hardware intensive, thus increasing the cost of the routers and decreasing their reliability.
Therefore, there is a need in the art for an improved Internet protocol (IP) router. In particular, there is a need for a massively parallel, distributed architecture router that is capable of minimizing the occurrence of out-of-sequence transmission of data packets from the router.